package cn.arnold.tree.threadtree;

// 线索二叉树
public class ThreadBinaryTreeDemo {
    public static void main(String[] args) {
        HeroNode2 root = new HeroNode2(1, "jina");
        HeroNode2 node1 = new HeroNode2(3, "jina");
        HeroNode2 node2 = new HeroNode2(6, "jina");
        HeroNode2 node3 = new HeroNode2(8, "jina");
        HeroNode2 node4 = new HeroNode2(10, "jina");
        HeroNode2 node5 = new HeroNode2(14, "jina");
        // 手动创建二叉树
        root.setLeft(node1);
        root.setRight(node2);
        node1.setLeft(node3);
        node1.setRight(node4);
        node2.setLeft(node5);
        // 测试中序线索化二叉树
        ThreadedBinaryTree threadedBinaryTree = new ThreadedBinaryTree();
        threadedBinaryTree.setRoot(root);
        threadedBinaryTree.threadedBodes();
        // 10号节点测试
        System.out.println("10号节点的前驱结点为："+node4.getLeft());
        System.out.println("10号节点的后继结点为："+node4.getRight());
        // 遍历线索化二叉树
        System.out.println("遍历中序线索化二叉树：");
        threadedBinaryTree.threadedList();
    }


}


class ThreadedBinaryTree {
    private HeroNode2 root;      // 根节点

    public HeroNode2 getRoot() {
        return root;
    }

    public void setRoot(HeroNode2 root) {
        this.root = root;
    }

    public void threadedBodes(){
        this.root=root;
    }

    private HeroNode2 preNode = null;    // 指向当前节点的前驱节点的指针

    /**
     * 遍历线索化二叉树
     */
    public void threadedList() {
        HeroNode2 tempNode = root;       // 存储当前遍历的节点，从root开始
        while (tempNode != null) {
            // 循环的找leftType为1的节点
            while (tempNode.getLeftType() == 0) {
                tempNode = tempNode.getLeft();
            }
            System.out.println(tempNode);
            // 如果当前节点的右指针指向的是后继节点，就一直输出
            while (tempNode.getRightType() == 1) {
                tempNode = tempNode.getRight();
                System.out.println(tempNode);
            }
            tempNode = tempNode.getRight();
        }
    }

    /**
     * 中序线索化节点
     *
     * @param node
     */
    public void threadedBodes(HeroNode2 node) {
        if (node == null) {
            return;
        }
        // (一)线索化左子树
        threadedBodes(node.getLeft());
        // (二)线索化当前节点
        // 1. 左子树为空则线索化前驱结点
        if (node.getLeft() == null) {
            // 当前节点的左指针指向前驱结点
            node.setLeft(preNode);
            // 修改当前节点左指针的类型
            node.setLeftType(1);
        }
        // 2. 处理后继节点
        if (preNode != null && node.getRight() == null) {
            // !!!前驱节点的右指针指向当前节点
            preNode.setRight(node);
            node.setRightType(1);
        }
        // !!!! 处理完每个节点后，让当前节点是下一个节点的前驱结点
        preNode = node;
        // (三)线索化右子树
        threadedBodes(node.getRight());
    }

}

// 节点对象
class HeroNode2 {
    private int id;
    private String name;
    private HeroNode2 left;      // 左节点，默认为null
    private HeroNode2 right;     // 右节点，默认为null

    private int leftType;       // 左节点指向子树：0; 指向前驱节点：1
    private int rightType;      // 右节点指向子树：0; 指向后继节点：1


    // 构造器
    public HeroNode2(int id, String name) {
        this.id = id;
        this.name = name;
    }

    public int getLeftType() {
        return leftType;
    }

    public void setLeftType(int leftType) {
        this.leftType = leftType;
    }

    public int getRightType() {
        return rightType;
    }

    public void setRightType(int rightType) {
        this.rightType = rightType;
    }

    public int getId() {
        return id;
    }

    public void setId(int id) {
        this.id = id;
    }

    public String getName() {
        return name;
    }

    public void setName(String name) {
        this.name = name;
    }

    public HeroNode2 getLeft() {
        return left;
    }

    public void setLeft(HeroNode2 left) {
        this.left = left;
    }

    public HeroNode2 getRight() {
        return right;
    }

    public void setRight(HeroNode2 right) {
        this.right = right;
    }

    @Override
    public String toString() {
        return "HeroNode{" +
                "id=" + id +
                ", name='" + name + '\'' +
                '}';
    }

}